package cn.com.leetcode.greedy;

import java.util.Arrays;

/**
 * 有一堆石头，每块石头的重量都是正整数。
 * <p>
 * 每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
 * <p>
 * 如果 x == y，那么两块石头都会被完全粉碎；
 * 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
 * 最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。
 * <p>
 *  
 * <p>
 * 示例：
 * <p>
 * 输入：[2,7,4,1,8,1]
 * 输出：1
 * 解释：
 * 先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]，
 * 再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]，
 * 接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]，
 * 最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/last-stone-weight
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Demo1046 {
    public static void main(String[] args) {
        Demo1046 demo1046 = new Demo1046();
        int[] stones = {2, 6, 6, 9, 4, 3};
        int lastStoneWeight = demo1046.lastStoneWeight(stones);
        System.out.println(lastStoneWeight);
    }

    public int lastStoneWeight(int[] stones) {
        //用来保存新的数据
        int[] newStones = stones;
        Arrays.sort(newStones);
        for (; newStones.length > 1; ) {
            int max_1 = newStones[newStones.length - 1];
            int max_2 = newStones[newStones.length - 2];
            int t = max_1 - max_2;
            int[] original = newStones;
            if (t == 0) {
                //每次都会创建一个新数组
                newStones = new int[newStones.length - 2];
                //将 stones 前 stones.length - 2 的数据依次复制到新数组 newStones 中
                copyArray(original, 0, newStones, 0, newStones.length);
            } else {
                //每次都会创建一个新数组
                newStones = new int[newStones.length - 1];
                int index = leftBoundBinarySearch(original, t, 0, original.length - 2);
                //original 0 ~ index - 1   arr 0 ~ index - 1
                //将数组 stones i 之前的数据依次插入到 newStones 数组 i 之前的位置
                copyArray(original, 0, newStones, 0, index);
                //arr index
                //将 newStone 插入到 newStones 的 i 位置
                newStones[index] = t;
                //将 stones i 之后的数据插入依次插入到 newStones i 之后的位置
                copyArray(original, index, newStones, index + 1, newStones.length - index - 1);
            }
        }
        return newStones.length == 0 ? 0 : newStones[0];
    }

    /**
     * @param originalArr   数据来源的数组
     * @param originalIndex 从数据来源的那个下标开始取值
     * @param targetArr     复制的目标数组
     * @param targetIndex   从目标数组的哪个下标开始赋值
     * @param len           需要赋值的长度
     */
    private void copyArray(int[] originalArr, int originalIndex, int[] targetArr, int targetIndex, int len) {
        for (int i = 0; i < len; i++) {
            targetArr[targetIndex + i] = originalArr[originalIndex + i];
        }
    }

    /**
     * 寻找左侧边界的二分搜索
     *
     * @param nums
     * @param target
     * @return
     */
    int leftBoundBinarySearch(int[] nums, int target, int l, int r) {
        if (nums.length == 0) return -1;
        int left = l;
        int right = r; // 注意

        while (left < right) { // 注意
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                right = mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid; // 注意
            }
        }
        return left;
    }
}
